package 力扣题库;

import java.util.LinkedList;
import java.util.Queue;

public class p222完全二叉树的节点个数 {
    public int countNodes1(TreeNode root) {
        if (root==null) {
            return 0;
        }
        if (root.right==null && root.left==null) {
            return 1;
        }

        return countNodes1(root.left)+countNodes1(root.right)+1;
    }

    //基于层序遍历的迭代法
    public int countNodes(TreeNode root) {
        if (root==null) {
            return 0;
        }

        Queue<TreeNode> queue=new LinkedList<>();//使用队列进行层序遍历
        queue.offer(root);

        int result=0;
        while (!queue.isEmpty()) {
            //当队列不为空时，处理当前层的结点
            int size=queue.size();
            while (size > 0) {
                result++;
                TreeNode cur=queue.poll();
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                size--;
            }
        }

        return result;
    }
}
